1. Field of the Invention
The present invention relates to a turbo encoded Hybrid Automatic Repeat reQuest (ARQ) system and an error detection method and, more particularly, to a turbo encoded Hybrid Automatic Repeat reQuest (ARQ) system and an error detection method which lowers undetected error probability and frame error rates by modifying trellis termination and thus by increasing the degree of the equivalent Cyclic Redundancy Check (CRC) generator polynomial.
2. Description of the Related Art
In general, as demand for high speed data transmission increases, a wireless communication system having high bandwidth efficiency and reliability is required. In order to satisfy such demand, a wireless communication system may employ a Hybrid Automatic Repeat reQuest (hereinafter, H-ARQ) method. The H-ARQ is a packet retransmission technique that assures high reliability communication by combining the Forward Error Correction (hereinafter, FEC) method and Automatic Repeat reQuest (hereinafter, ARQ) method.
Here, the FEC is a technique by which errors deemed to have occurred at the channel are corrected through the use of the structural characteristic of the code. The term ‘forward’ in the FEC is originated from the characteristics that, even if errors occur at a received frame, a receiver does not request additional information for correcting errors from the transmitter but, rather, corrects errors at the receiver independently to the maximum extent possible. That is to say, in the FEC, even if there are errors that have not been corrected after decoding, the decoding result is processed to the next step without a request for retransmission.
The H-ARQ transmits message symbols to be transmitted, parity symbols for error correction and parity symbols for error detection. The H-ARQ is divided into two types: type 1 H-ARQ and type 2 H-ARQ depending on what order the parity symbols are transmitted.
The type 1 H-ARQ is a method of transmitting message symbols, parity symbols for error correction and parity symbols for error detection together at the same time on every transmission. In type 1, because frames always having the same structure are transmitted, there is an advantage that the structure of the transmitter and the receiver is simple, although adaptability to a channel situation may be inferior.
On the other hand, the type 2 H-ARQ is a method of transmitting message symbols and parity symbols for error detection on the first transmission and transmitting parity symbols for error correction only when the receiver requests retransmission. Because the type 2 H-ARQ transmits parity symbols for error correction only when errors have occurred, the system operates flexibly by being adaptive to a channel situation and thus the overall efficiency of the system is superior to that of the type 1 H-ARQ.
Hereinafter, it will be explained with reference to FIG. 1 as to a turbo encoded H-ARQ system of the related art to which the H-ARQ is applied. Particularly, the system adopting the type 1 H-ARQ will primarily be explained.
FIG. 1 is a block diagram that illustrates a turbo encoded H-ARQ system in the related art.
The related art turbo encoded H-ARQ system comprises a transmitter (10) and a receiver (20). The transmitter (10) comprises a turbo encoder (11) that turbo-encodes packets to be transmitted, and the receiver (20) comprises a turbo decoder (21) that performs the FEC against errors included in received packets, and an error detector (22) detects whether errors are included in the corrected packets and transmits signals requesting retransmission of packets to the transmitter (10), if there are errors in the corrected packets.
Hereinafter, the operation of the related art turbo encoded H-ARQ system having the above-explained structure will be explained.
First, the transmitter (10) turbo-encodes a packet to be transmitted by using the turbo encoder (11) and transmits the turbo encoded packet through the channel to the receiver (20). In the type 1 H-ARQ, each transmitted packet includes additional bits for error correction and error detection.
Then, the receiver (20) receives the packet transmitted through the channel. Thereafter, the turbo decoder (21) performs FEC against errors included in the received packet.
The error detector (22) detects whether errors are included in the corrected packet and transmits a signal requesting retransmission of the packet to the transmitter (10) if there are errors in the corrected packet. In other words, if it is determined that no error exists in the corrected packet, an ACKnowledgment (hereinafter, ACK) signal is sent back to the transmitter (10). On the other hand, if it is determined that errors exist in the corrected packet, a Not AcKnowledgment (hereinafter, NAK) signal is sent back to the transmitter (10).
Accordingly, the transmitter (10) receives ACK signals and NAK signals, which are signals related to request for retransmission of packets, and retransmits relevant packets to the receiver (20) according to the relevant received signals. In other words, if the transmitter (10) receives an ACK signal, the transmitter does not retransmit any packet to the receiver (20). On the other hand, if the transmitter (10) receives a NAK signal, the transmitter retransmits a packet having the same structure as the packet transmitted previously by the transmitter to the receiver (20) (See e.g., S. Lin and J. Costello, Error Control Coding: Fundamentals and Applications. Prentice-Hall, 1985).
Particularly, if the Chase Combining, which performs decoding by considering a set of codes received on every transmission as one code having a lower code rate, is employed, the performance of type 1 H-ARQ is improved remarkably (See, D. Chase, “Code combining a maximum-likelihood decoding approach for combining an arbitrary number of noisy packets,” IEEE Trans. Commun., vol. 33, No. 2, 385–393, May 1985).
On the other hand, it is known that a turbo code suggested first in 1993 by Berrou et al. shows the superior error correction performance, which approaches the Shannon Limit.
Hereinafter, one example of a turbo encoder (11) structure illustrated in FIG. 1 will be explained with reference to FIG. 2.
FIG. 2 is a diagram illustrating the structure of the related art turbo encoder (11) illustrated in FIG. 1.
In the related art turbo encoder (11), at least two Recursive Systematic Convolution Encoders (Hereinafter, “RSC encoders”) (12, 13) are combined in parallel with an interleaver (14) in between RSC encoders.
Because residual errors after the turbo encoding are detected through the error detector (22) in the related art turbo encoded H-ARQ system illustrated in FIG. 1, the related art turbo encoded H-ARQ system has a lower error floor than pure turbo encoded systems.
On the other hand, a number of error detection methods that do not require additional overhead bits in the turbo encoded H-ARQ system have been suggested, for example, M. E. Buckley and S. B. Wicker, “The design and performance of a neural network for predicting turbo decoding error with application to hybrid ARQ protocols,” IEEE Trans. Commun., vol. 48, No. 4, 566–576, April 2000, and P. Coulton, C. Tanriover, B. Wright, and B. Honary, “Simple hybrid type 2 H-ARQ technique using soft output information,” Electron. Lett., vol. 36, No. 20, 1716–1717, September 2000. However, these error detection methods have higher undetected error probabilities than the CRC error detection method. The CRC error detection method adds parity symbols for error detection to message symbols to be transmitted and determines whether errors exist by using the structure of the parity symbol for error detection with the hard decision value made on the FEC encoded frame at a receiver. The parity symbol for error detection is added to the message symbol using a CRC encoder. The above-mentioned undetected error probability means the probability of making a wrong decision that errors do not exist in the frame in which errors actually exist. The high undetected error probability results in high frame error rates in H-ARQ systems.
Hereinafter, an explanation will be given with reference to FIG. 3 as to the related art CRC error detection method applied to a turbo encoded H-ARQ system.
FIG. 3 is a block diagram illustrating the CRC error detection method in a related art turbo encoded H-ARQ system.
A turbo encoded H-ARQ system, to which the related art CRC error detection method applies, comprises a transmitter (10) and a receiver (20).
Here, the transmitter (10) comprises a CRC encoder (15), a turbo encoder (11) and a modulator (16). The CRC encoder (15) CRC encodes message symbols to be transmitted into new message symbols by adding parity symbols for error detection to the message symbols to be transmitted. The turbo encoder (11) turbo encodes the CRC encoded new message symbols. The modulator (16) modulates the CRC encoded and turbo encoded new message symbols to channel symbols and transmits the CRC encoded and turbo encoded new message symbols to the receiver (20).
The receiver (20) comprises a demodulator (23), a turbo decoder (21) and a CRC decoder (24). The receiver (20) receives the modulated channel symbols, demodulates the received channel symbols to CRC encoded and turbo encoded new message symbols. The turbo decoder (21) turbo decodes the demodulated CRC encoded and turbo encoded new message symbols to CRC encoded new message symbols. The CRC decoder (24) CRC decodes the turbo decoded frame, detects whether there are errors included in the CRC decoded frame and transmits a signal requesting retransmission of symbols to the transmitter (10) according to the existence of errors.
Hereinafter, an explanation will be given as to a turbo encoded H-ARQ system, having the above-explained structure, to which the related art CRC error detection method is applied.
First, the CRC encoder (15) in the transmitter (10) performs CRC encoding, generating new message symbols by adding parity symbols for error detection to message symbols to be transmitted, using a CRC generator polynomial.
In order to illustrate the CRC encoding, the sequence of the message symbol can be expressed as i(x) and the CRC generator polynomial can be expressed as gCRC(x). Then, assume that the CRC encoder (15) has the following CRC generator polynomial gCRC(x).gCRC(x)=1+c1x+c2x2+ . . . +cn−k−1xn−k−1+xn−k  [Equation 1]
Then, the CRC encoding process may be expressed as follows.
                                                                                          i                  1                                ⁡                                  (                  x                  )                                            =                                                                    i                    ⁡                                          (                      x                      )                                                        ⁢                                      x                                          n                      -                      k                                                                      +                                  P                  ⁡                                      (                    x                    )                                                                                                                          =                                                i                  ⁡                                      (                    x                    )                                                  ⁢                                                      g                    CRC                                    ⁡                                      (                    x                    )                                                                                                          [                  Equation          ⁢                                          ⁢          2                ]            
Here, p(x) means the sequence of a parity symbol added to the ending part of a message symbol in the CRC encoder (15) and i1(x) means the sequence of the new message symbol to which the parity symbol is added through CRC encoding.
Thereafter, the turbo encoder (11) turbo encodes the CRC encoded new message symbols.
The modulator (16) modulates the CRC encoded and turbo encoded new message symbols to channel symbols and transmits the modulated channel symbols to the receiver (20). In other words, i1(x), the CRC encoded new message symbol at the CRC encoder (15), is turbo encoded at the turbo encoder (11), modulated to a channel symbol at the modulator (16) and transmitted to the receiver (20).
Then, the demodulator (23) in the receiver (20) receives the modulated channel symbols and demodulates the received channel symbols to the CRC encoded and turbo encoded new message symbols.
The turbo decoder (21) turbo decodes the demodulated CRC encoded and turbo encoded new message symbols and outputs a hard decision value made upon the frame of the CRC encoded new message symbols. At this time, the hard decision value outputted, after going through the channel and demodulation, from the turbo decoder (21) for FEC is as follows.
                                                                                          i                  ^                                ⁡                                  (                  x                  )                                            =                                                                    i                    1                                    ⁡                                      (                    x                    )                                                  +                                  e                  ⁡                                      (                    x                    )                                                                                                                          =                                                                    i                    ⁡                                          (                      x                      )                                                        ⁢                                                            g                      CRC                                        ⁡                                          (                      x                      )                                                                      +                                  e                  ⁡                                      (                    x                    )                                                                                                          [                  Equation          ⁢                                          ⁢          3                ]            
Here, î(x) is the sequence of a CRC encoded new message symbol, which has been turbo decoded, that is to say, has passed through the forward error correction. e(x) is the error sequence.
CRC decoder (24) CRC decodes the turbo decoded symbol frame, detects whether there are any errors in the CRC decoded frame and transmits a signal requesting retransmission of the symbol to the transmitter (10) according to the existence of errors.
More particularly, the CRC decoder (24) detects errors by dividing î(x) by gCRC(x), which is the CRC generator polynomial used in the CRC encoding. If the error sequence e(x) is zero (that is to say, if no error exists in the FEC processed frame), î(x) may be divided by gCRC(x) without any remainder. On the other hand, if the error sequence e(x) is not zero (that is to say, if errors exist in the FEC processed frame), diving î(x) by gCRC(x) leaves a remainder. In other words, e(x)mod gCRC(x) is left after the division.
Accordingly, the CRC decoder (24) transmits an ACK signal to the transmitter (10) based on the determination of the CRC decoder (24) that no error has occurred if î(x) may be divided by CRC generator polynomial gCRC(x) without any remainder. On the other hand, the CRC decoder (24) transmits a NAK signal to the transmitter (10) based on the determination of the CRC decoder (24) that errors have occurred if î(x) is not divided by the CRC generator polynomial gCRC(x).
When detecting errors using the CRC decoder (24) as described above, the detecting standard is as follows.
                                                                                                              i                    ^                                    ⁡                                      (                    x                    )                                                  ⁢                mod                ⁢                                                                  ⁢                                                      g                    CRC                                    ⁡                                      (                    x                    )                                                              =                                                {                                                                                    i                        ⁡                                                  (                          x                          )                                                                    ⁢                                                                        g                          CRC                                                ⁡                                                  (                          x                          )                                                                                      +                                          e                      ⁡                                              (                        x                        )                                                                              }                                ⁢                mod                ⁢                                                                  ⁢                                                      g                    CRC                                    ⁡                                      (                    x                    )                                                                                                                          =                                                e                  ⁡                                      (                    x                    )                                                  ⁢                mod                ⁢                                                                  ⁢                                                      g                    CRC                                    ⁡                                      (                    x                    )                                                                                                          [                  Equation          ⁢                                          ⁢          4                ]            
According to the above description, the transmitter (10) receives ACK and NAK signals, which are signals related to request for retransmission of symbols, and retransmits message symbols to the receiver (20) according to the type of the received signals. In other words, if the transmitter (10) receives an ACK signal, the transmitter does not retransmit any message symbol to the receiver (20). On the other hand, if the transmitter receives a NAK signal, the transmitter retransmits to the receiver (20) a message symbol having the same structure with the message symbol previously transmitted.
There are problems in the above-described related art turbo encoded H-ARQ system in that additional overhead bits are required in order to achieve a low undetected error probability. Also, the throughput of the related art turbo encoded H-ARQ system is lowered as the number of overhead bits increases. Further, frame error rates are increased by the increase of the undetected error probability of the turbo encoded H-ARQ system if the number of overhead bits is maintained small in order to improve the throughput.